/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  //特殊情况处理
  if (matrix.length === 0) return 0

  //行数 列数
  let m = matrix.length
  let n = matrix[0].length
  //最大边
  let maxSide = 0
  //滚动动态方程（压缩成一维，节省空间复杂度）
  let dp = new Array(n).fill(0)

  for (let i = 0; i < m; i++) {
    // 记录左上角的dp值（即dp[i-1][j-1]）
    let prev = 0
    for (let j = 0; j < n; j++) {
      //暂存当前dp[j]，作为下一轮的prev
      let temp = dp[j]
      if (matrix[i][j] === '1') {
        if (i === 0 || j === 0) {
          dp[j] = 1
        } else {
          //状态转移方程：取左边、对角线、上面三者的最小值，然后+1
          dp[j] = Math.min(dp[j - 1], prev, dp[j]) + 1
        }
        //更新prev
        prev = temp
        //更新最大边
        maxSide = Math.max(maxSide, dp[j])
      } else {
        dp[j] = 0
      }
    }
  }

  //返回最大面积
  return maxSide * maxSide
};